1. Field of the Invention
This invention relates to memory management in computer systems, and more particularly to garbage collection in a memory system.
2. Background Art
A typical computer system consists of a number of modules or components. Computer systems typically include a central processing unit (CPU) such as a microprocessor. The microprocessor is a program-controlled device that obtains, decodes and executes instructions. A computer system also includes program storage components for storing program instructions, and data storage components for storing data. These storage components may be read only memory (ROM), random access memory (RAM), disk or tape storage, or any other suitable storage means.
A computer system typically also includes input/output (I/O) components for connecting external devices to the microprocessor. Special purpose components, such as memory management units or co-processors, may also be part of the computer system.
The memory component, also known as a "main memory," is a scarce resource that is dynamically allocated to users, programs or processes. Main memory is typically a silicon-based memory such as a RAM. In many applications, dynamic random access memory (DRAM) is used as the main memory. Processor main memory is "byte" organized. That is, memory is arranged as a sequence of 8-bit bytes and the byte is the smallest unit of information accessed out of the memory. In one convention, an entire row is selected by a row address and columns are accessed in groups of 8 bits. In some implementations, 16-bit words (2 bytes) or 32-bit words (4 bytes) are accessed at one time. The bytes or words in the memory which are uniquely addressable make up the address space of the memory.
Within the computer system, the processor uses associated memory storage locations for the temporary storage of data and/or instructions. The contents of the memory are changing over time so that, at different times, a memory location may be "allocated" (used) or "unallocated" (unused).
Allocated memory locations are those locations that contain instructions or data such as program code, or those that are referenced, ("pointed to"), by another allocated location. Locations that point to other locations are known as "pointers" and include the address of the location they point to as part of their stored information. The memory addresses of unallocated locations are not found in the storage space of other locations unless, by coincidence, the data stored at another location is the binary equivalent of the unallocated memory address. Unallocated memory locations constitute reclaimable or usable memory space.
To promote efficient memory usage, unallocated memory locations must be "reclaimed" so that they can be allocated. The identification and reclaiming of unallocated memory locations is known as "garbage collection," and can be accomplished by a variety of methods. A system or method for performing such garbage collection is referred to as a "garbage collector."
In one method, a garbage collector in a computer system determines if an object is garbage by scanning the entire address space of memory and comparing the value found in each scanned memory address to a memory address that is a candidate for garbage. If no match is found, the candidate for garbage is not referenced and therefore, is garbage. If a match is found, it is assumed that the memory location is referenced and therefore not garbage. Coincidental matches fall under this assumption and are not collected. Therefore, in the worst case, some "garbage" may elude collection, but no referenced locations are mistakenly collected. For this reason, this method is known as a "conservative scan." It is also called a "mark and sweep" method, because the collector processes all addresses, marking the ones that are free for allocation, then the collector places the marked addresses on a "free" list. The time required to complete this process is proportional to the size of the memory being collected.
In the past, computer systems operated on relatively small memory spaces, and the reclamation of memory space was not a significant problem. When the memory was in need of garbage collection, the CPU processes were halted and a garbage collection process, such as a conservative scan, was performed. Presently, however, larger memories are being implemented, especially with applications that are memory intensive. Thus, the problems associated with garbage collection have become of greater significance. It is desirable to have a garbage collecting process which does not require an extended interruption of CPU processes.
One method for performing garbage collection without extended interruptions involves using a reference count for each memory address. This method is described in U.S. Pat. No. 4,912,629 to Robert Shuler, Jr. The reference count indicates the number of other addresses that include a pointer to that address. Whenever a new pointer to an address is created, the reference count of the address is incremented by one, and whenever an existing pointer is destroyed, the reference count of the address to which it points is decremented by one. Addresses whose reference counts become equal to zero are reclaimed by adding them to a list of free addresses.
Reference counting has a desirable feature in that garbage collection is accomplished at the earliest possible moment. Furthermore the reclamation is spread over time rather than being executed in a single long, and potentially disruptive, operation. However, reference counting cannot reclaim unused data objects that are linked into a circular structure nor data objects whose reference counts have overflowed. Also, the computational effort expended with reference counting is proportional to the number of dead data objects in the systems memory, placing large demands upon the system CPU. Another problem exhibited by the reference count method is one of timing. For example, consider the multi-processor system shown in FIG. 1.
FIG. 1 shows a multi-processor distributed computer system. The system comprises a plurality of processors (processor 1, processor 2, etc.) interconnected by a switch (100) that allows messages to be passed between the processors. Each processor includes a memory (11, 12, 13, etc.) for holding programs and data words. Each processor performs operations based upon the programs within its memory and the messages sent from other processors. It is possible in this system for memory words in one processor to point to words in another processor. A first processor containing a pointer sends messages via switch 100 to a second processor containing the word referenced by the pointer for the purpose of notifying the second processor when to increment and decrement the reference count of the referenced word.
In this system, different words in a reference graph structure may reside in different processors. For example, in FIGS. 2A-2C, words 200 and 201 may reside in processor 1, while word 202 resides in processor 2. In the initial situation, word 200 points to word 201, giving word 201 a reference count of one (FIG. 2A). When word 202 is created, processor 2 sends a message to processor 1, telling it to increment the reference count of word 201 (FIG. 2B). Similarly, when word 202 is destroyed, processor 2 sends a second message to processor 101, telling it to decrement the reference count of word 201 (FIG. 2C). Each message takes a finite time to reach processor 1, thus an error can occur if the second message is acted upon before the first message.
FIGS. 3A-3D show what happens when the messages are acted upon in the wrong order. FIG. 3A shows the same initial situation as in FIG. 2A. In FIG. 3B, word 202 has been created, with a pointer to word 201, but the message to increment the reference count of word 201 has not yet arrived. In FIG. 3C, word 202 has been garbage collected, and the message to decrement the reference count of word 201 has arrived; the reference count for word 201 is, therefore, now zero. Finally, in FIG. 3D, the first message has now arrived, causing the reference count of word 201 to be incremented to one.
If a garbage collection occurs while the situation of FIG. 3C exists, word 201 is collected in error, and the reference count is incorrect from then on. Reference count systems designed to avoid this issue are very complex in their implementation. It is desirable to have a garbage collecting process that is reliable and simplistic in design.
U.S. Pat. No. 4,755,939 to Watson describes a computer system having memory cells (or words) organized in a directed graph structure by means of pointers. Each cell has a reference count, and each pointer has a weight value. If a new pointer to a cell is created by copying an existing pointer, the new and existing pointers are given weights whose sum equals the old value of the existing pointer. In this way, the sum of the weights of the pointers to any cell are maintained equal to its reference count. When a pointer is destroyed, the reference count of the cell to which it points is reduced by the weight of the pointer. When the reference count of a cell reaches zero, it is reclaimed (garbage-collected) for re-use.
U.S. Pat. No. 4,757,438 to Thatte et al. describes a computer system which enables automatic memory operations independently of the CPU. The computer system includes a virtual machine and a logical memory system which is accessed by the virtual machine through a binding registry unit.
Another method used in many commercial list processing systems, described in U.S. Pat. No. 4,775,932 to Oxley et al., is known as "stop and copy", which works by copying live data objects from the space being collected into an unused space. With reference to FIGS. 4A-4D, this method separates the memory into two equally-sized spaces (401,402). All allocation takes place from one of the spaces known as "oldspace" (401). The second space (402), known as "newspace", remains empty until garbage collection begins. When oldspace 401 is completely allocated, the user computation is stopped and garbage collection begins (FIG. 4A-4B). The base set 400 is scanned looking for references (i.e. 403) into oldspace 401. When a reference is found, the collector determines if there is a forwarding pointer (i.e. 404) where the data object should be. If there is a forwarding pointer (i.e. 405), the original reference is updated to point where specified by the forwarding pointer and the collector proceeds with the scan of the base set 400. If the data object (i.e. "3.14") is in oldspace 401, it is copied to the next available location (406) in newspace 402, a forwarding pointer (407) is placed at the old location in oldspace 401 to indicate where the data object was copied to, and the original reference (408) is updated to reference the moved data object.
When the base set has been completely scanned, newspace can be linearly scanned for references (409) from copied objects into oldspace 401. As references are found into oldspace 401, the data objects (i.e. "42") are copied to newspace (if they have not already been copied) and the reference is updated to reflect the new location 410 (FIG. 4C). Since newspace 402 is scanned from the same end that allocation first occurred and the scan is in the direction of new allocation, data objects copied during the scan will always be placed at the end of newspace 402 where the collector has yet to scan. When the scanning pointer reaches the new allocation pointer, the garbage collection is complete.
At this stage, all references into oldspace 401 are gone; all that remain are dead objects and forwarding pointers. Oldspace 401 and newspace 402 are interchanged and the user computation can continue. The interchange of the spaces reclaims all space in oldspace 401 for use as newspace during the next collection (FIG. 4D). This algorithm permits only half of the available dynamic data memory to be allocated before a garbage collection must take place; the second half of the memory remains idle and empty, waiting for copying to occur.
A disadvantage of the stop and copy scheme is that of having to actually access the heap when a reference to oldspace is encountered. The least predictable accessing in garbage collection is that involved with marking or determining if a data object needs to be copied. If there is only one reference in existence for each data object, the same number of heap references are required for the "mark and sweep" and the "stop and copy" schemes. However, there is often more than one reference to a data object. In the mark and sweep scheme, a small table of mark bits can used to avoid actually making accesses to a large heap for any but the first reference mark encountered. The stop and copy scheme essentially requires making random heap accesses to obtain the forwarding information.
Another disadvantage of stop and copy garbage collectors is that these collectors cannot be used in computer systems that have "ambiguous roots" (i.e. objects in the root which may or may not be pointers). An ambiguous root may in fact be a piece of data, such as a loop counter. Since all accessible objects are copied and moved to new locations in memory, all pointers to the accessible objects must be found and changed so that these pointers continue to point to the appropriate objects.
It is unacceptable for an object which might be a pointer, but is in fact a data value, to be changed in value by the garbage collector. Thus, the stop and copy collector must be able to distinguish between pointers and other data, and must be able to find all pointers to accessible objects. This requirement is sometimes called "root finding". In some implementations, root finding is not a problem, and thus a stop and copy garbage collector can be used. However, other computer environments present more serious problems in finding roots.
In U.S. Pat. No. 4,797,810 to McEntee, et al., the garbage collector is generational and implements a stop and copy collection scheme. Each area in the individual address space is divided in up to four generations, with the youngest generation being the most volatile and resident in the main computer memory. During the copying of objects from old space to new space, objects are "tenured" or promoted from one generation to an older generation. An object is promoted when it has survived a predetermined number of garbage collections, thereby demonstrating that it likely will not be reclaimed by the collector in the immediate future. Thus, the garbage collector operates on an area-by-area basis upon objects which are contained in one of two semi-spaces; old space or new space, and during the garbage collection process, all accessible objects are copied from old space to new space.
In the collection scheme of McEntee et al., the garbage collector and the virtual memory processes can act on memory concurrently. Consequently, the garbage collector operates incrementally in distinction to "pausing" collectors. This method still exhibits the problems of a standard "stop and copy" system, in that it still requires fairly random heap accesses to obtain forwarding information and the ability to recognize ambiguous roots.
Other U.S. patents related to this issue are: U.S. Pat. Nos. 4,757,438; 4,807,120; 4,814,971; 4,907,151; 4,961,137; 4,989,134; and 4,989,137.
U.S. Pat. No. 4,807,120 to Courts describes a garbage collection system for digital computers that classifies memory objects into generations. Objects in older generations that need to reference younger generations must do so indirectly through indirection cells located in the older generation. When a generation is collected, the indirection cells in that generation are defined to be old space and collected in the usual manner. The system also includes read and write barriers which function to filter out undesirable pointers based on the classification and volatility of memory regions to which they point or are destined to be stored.
U.S. Pat. No. 4,814,971 to Thatte describes a virtual memory recovery system in which periodic check points are taken of the state of the computer system and its virtual memory. If a system crash occurs, the machine state can be rolled back to the check point state and normal operation is restarted. In the garbage collection system of Thatte, deleted objects are specially marked as "tombstoned" when they are deleted. All of the outstanding pointers to a tombstoned block are detected by the garbage collector and then destroyed. When no pointers to a tombstoned block are left its space is automatically reclaimed.
U.S. Pat. No. 4,907,151 to Bartlett describes a garbage collection method providing a heap of storage space for storing program objects generated by a task. A root storage area stores information including ambiguous pointers which may or may not point to program objects stored in the heap. Garbage collection is performed by promoting and retaining all pages in the heap which are referenced by hints within the root storage area, and by copying into previously unallocated pages all other accessible program objects in the heap.
U.S. Pat. No. 4,961,137 to Augusteijn et al. describes a method and apparatus for establishing a global binary assertion in a multi-processor environment. The logical operation may represent a garbage collection system, wherein originally root items are marked gray and all other items white. In a marking phase, all gray items are successively accessed. After verifying any other item referred to by such gray item, and if white, discoloring the other item to gray, the original item is discolored to black. When no gray items are left globally, the remaining white objects are treated as garbage.
U.S. Pat. No. 4,989,134 to Shaw describes a method for enhancing data storage efficiency by reducing a base set to be garbage collected. To facilitate this, the system utilizes "dirty page mapping". Dirty page maps contain a listing of all locations in a memory region, or page, that have been written to since the last garbage collection process. A secondary memory dirty page map and a primary memory dirty page map are developed and utilized to reduce the size of the base set by allowing the garbage collection routine to ignore any page in the base set which has not been written to.
U.S. Pat. No. 4,989,137 to Oxley et al. describes a computer memory system for use with a user processor that provides for automatic memory operation independent of the user processor. The user cannot access the memory directly, but must access the memory through a binding register unit. The logical memory system is controlled by a separate memory management unit which manages the physical memory of the system and which manages the memory to have the logical memory system appearance to the user processor. Garbage collection is performed automatically without requiring that the ongoing processing steps of the user processor be halted during the garbage collection process.